Data-Oblivious External-Memory Algorithms for the Compaction, Selection, and Sorting of Outsourced Data

摘要

We present data-oblivious algorithms in the external-memory model forcompaction, selection, and sorting. Motivation for such problems comes fromclients who use outsourced data storage services and wish to mask their dataaccess patterns. We show that compaction and selection can be donedata-obliviously using $O(N/B)$ I/Os, and sorting can be done, with a highprobability of success, using $O((N/B)\log_{M/B} (N/B))$ I/Os. Our methods usea number of new algorithmic techniques, including data-oblivious uses ofinvertible Bloom lookup tables, a butterfly-like compression network,randomized data thinning, and "shuffle-and-deal" data perturbation. Inaddition, since data-oblivious sorting is the bottleneck in the "inner loop" inexisting oblivious RAM simulations, our sorting result improves the amortizedtime overhead to do oblivious RAM simulation by a logarithmic factor in theexternal-memory model.